package LeetCode;

public class LC_148_SortList {

    public static void main(String[] args) {

    }

    static class Solution {
        ListNode sortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            ListNode middle = getMiddleOfList(head);
            ListNode next = middle.next;
            middle.next = null;
            return mergeTwoList(sortList(head), sortList(next));
        }

        private ListNode mergeTwoList(ListNode headA, ListNode headB) {
            ListNode fakeNode = new ListNode(-1);
            ListNode cur = fakeNode;
            while (headA != null && headB != null) {
                if (headA.val <= headB.val) {
                    cur.next = headA;
                    headA = headA.next;
                } else {
                    cur.next = headB;
                    headB = headB.next;
                }
                cur = cur.next;
            }
            cur.next = headA == null ? headB : headA;
            return fakeNode.next;
        }

        private ListNode getMiddleOfList(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

}